package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/3/13 16:22
 * @description：https://leetcode-cn.com/problems/utf-8-validation/
 */
public class UTF8编码验证 {
    @Test
    public void test() {
        Solution solution = new Solution();

        System.out.println(solution.validUtf8(new int[]{235,140,4}));
    }


    /*
    class Solution {
        public boolean validUtf8(int[] data) {
            int len = data.length;
            String[] dataStrs = new String[len];
            for (int i = 0; i < len; i++) {
                if (data[i] < 128) {
                    StringBuilder s = new StringBuilder(Integer.toBinaryString((1 << 8) | data[i]));
                    s.replace(0, 1, "0");
                    dataStrs[i] = s.toString();
                } else {
                    dataStrs[i] = Integer.toBinaryString(data[i]);
                }
            }
            int idx = 0;
            while (idx < len) {
                String curStr = dataStrs[idx];
                int indexOfZero = curStr.indexOf("0");
                if (indexOfZero == 0) {
                    idx++;
                    continue;
                }
                if (indexOfZero == -1 || indexOfZero > 4 || indexOfZero == 1) return false;
                int nextIdx = idx + indexOfZero;
                if (nextIdx > len) return false;
                idx++;
                while (idx < nextIdx) {
                    if (dataStrs[idx].charAt(0) != '1' || dataStrs[idx].charAt(1) != '0') {
                        return false;
                    }
                    idx++;
                }
            }
            return true;
        }
    }
     */

    class Solution {
        static final int MASK1 = 1 << 7;
        static final int MASK2 = (1 << 7) + (1 << 6);

        public boolean validUtf8(int[] data) {
            int len = data.length;
            int idx = 0;
            while (idx < len) {
                int num = data[idx];
                int n = getBytes(num);
                if (n < 0 || n + idx > len) {
                    return false;
                }
                for (int i = 1; i < n; i++) {
                    if(!isValid(data[idx + i])) {
                        return false;
                    }
                }
                idx += n;
            }
            return true;
        }


        private int getBytes(int num) {
            if ((num & MASK1) == 0) {
                return 1;
            }
            int n = 0;
            int mask = MASK1;
            while ((num & mask) != 0) {
                n++;
                if (n > 4) {
                    return -1;
                }
                mask >>= 1;
            }
            // 过滤n = 1的情况
            return n >= 2 ? n : -1;
        }

        private boolean isValid(int num) {
            return (num & MASK2) == MASK1;
        }
    }
}
